sup-extra CodeForce-1009E Dominant Indices 启发式合并

Posted at 2019-01-21 ICPC 

CodeForce-1009F Dominant Indices 启发式合并

---

写这个题的时候至少进行了一亿次心理博弈……

题意大致为：对以节点x为根形成的子树，找到节点最多的层数，要是有多个数值相同就取最小的。

虽然看得出来是启发式合并解法，但是写的时候对于到底要怎么更新存储的最大值和结果一直没想明白……一开始写的是在求完所有的点之后遍历一遍去找最大的值，但是发现当树过长的时候时间复杂度是O(N!）……翻了很多博客都是寻找重儿子后进行一次交换，保留重儿子的结果再进行加，于是我开始思考我能不能在 每次遇到比我的层数多的子树时，交换子树统计的每层点的个数，同时拿过来子树的最大值呢。

我原本的想法：

要是我现在的最大层为a1,交换后成了一个比它小的b1，然后加的时候没遇到a1这一层那最大值不就错了嘛。

然后发现既然能进行交换那进行合并的时候肯定会更新a1这一层的值……因为交换了之后还要把原本的各层加回去……

稍微更改一下思路就过了。

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#define maxl 1000006
using namespace std;
typedef long long LL;
int n,res[maxl],most[maxl];
map<int,int> cal[maxl];
vector<int> tree[maxl];
void dfs(int s,int depth,int e)
{
    cal[s][depth]=1;
    for(int i=0;i<tree[s].size();i++)
    {
        int v=tree[s][i];
        if(v==e) continue;
        dfs(v,depth+1,s);
        if(cal[s].size()<cal[v].size())
        {
            swap(cal[s],cal[v]);
            most[s]=most[v];
            res[s]=res[v]+1;
        }
        for(map<int,int>::iterator it=cal[v].begin();it!=cal[v].end();it++)
        {
            int tmp=it->first;
            cal[s][tmp]+=it->second;
            if(cal[s][tmp]>most[s])
            {
                res[s]=tmp-depth;
                most[s]=cal[s][tmp];
            }
            else if(cal[s][tmp]==most[s]&&res[s]>(tmp-depth))
                res[s]=tmp-depth;
        }
    }
}
int main(void)
{
    while(~scanf("%d",&n))
    {
        int a,b;
        memset(res,0,sizeof(res));
        for(int i=1;i<=n;i++)
            most[i]=1;
        for(int i=1;i<=n;i++)
        {
            tree[i].clear();
            cal[i].clear();
        }

        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        dfs(1,1,0);
        for(int i=1;i<=n;i++)
            printf("%d\n",res[i]);
    }
	return 0;
}